package com.codes.patch.utils;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.codes.patch.file.FileEntry;

public class PatchGenerator {
	
	public static class Tire {
		private Map<Character, Tire> mNext = new HashMap<>();
		private List<Integer> mEndIndexs = new ArrayList<>();
		
		public void insert(String s, int endIndex) {
			if (TextUtils.isEmpty(s)) {
				return ;
			}
			
			Tire rootTire = this;
			for (int i = 0; i < s.length(); ++i) {
				char key = s.charAt(i);
				Tire childTire = rootTire.mNext.get(key);
				if (childTire == null) {
					childTire = new Tire();
					rootTire.mNext.put(key, childTire);
				} 
				rootTire = childTire;
			}
			rootTire.mEndIndexs.add(endIndex);
		}
		
		public List<Integer> getEndIndexs(String s) {
			if (TextUtils.isEmpty(s)) {
				return new ArrayList<>();
			}
			Tire rootTire = this;
			for (int i = 0; i < s.length(); ++i) {
				char key = s.charAt(i);
				rootTire = rootTire.mNext.get(key);
				if (rootTire == null) {
					break;
				} 
			}
			if (rootTire == null) {
				return new ArrayList<>();
			} else {
				return rootTire.mEndIndexs;
			}
		}
	}

	public boolean makePatch(FileEntry fileOld, FileEntry fileNew, FileEntry filePatch) {
		if (!checkParams(fileOld, fileNew, filePatch)) {
			return false;
		}
		
		Tire rootTire = new Tire();
		makeTireTree(rootTire, fileOld.getLineList());
		
		List<Integer> sequence = new ArrayList<>();
		List<Integer> indexWidth = new ArrayList<>();
		
		makeSequenceMap(rootTire, fileNew.getLineList(), sequence, indexWidth);
		
		List<Integer> answerPosition = new ArrayList<>();
		LISUtil.LIS(sequence, answerPosition);
		
		List<Integer> oldSamePos = new ArrayList<>();
		List<Integer> newSamePos = new ArrayList<>();
		makeSamePosition(sequence, answerPosition, indexWidth, oldSamePos, newSamePos);
	
		List<String> patchLineList = new ArrayList<>();
		makePatchLineList(fileOld.getLineList(), fileNew.getLineList(), oldSamePos, newSamePos, patchLineList);
		
		filePatch.setLineList(patchLineList);

		return true;
	}
	
	private boolean checkParams(FileEntry fileOld, FileEntry fileNew, FileEntry filePatch) {
		return fileOld != null && fileNew != null && filePatch != null;
	}
	
	private void makeTireTree(Tire rootTire, List<String> lineList) {
		if (rootTire == null || lineList == null) {
			return ;
		}
	
		for (int i = 0; i < lineList.size(); ++i) {
			String lineString = lineList.get(i);
			rootTire.insert(lineString, i);
		}
	}
	
	private void makeSequenceMap(Tire rootTire, List<String> lineList, List<Integer> sequence, List<Integer> indexWidth) {
		if (rootTire == null || lineList == null || sequence == null || indexWidth == null) {
			return ;
		}
		
		for (int i = 0; i < lineList.size(); ++i) {
			String lineString = lineList.get(i);
			List<Integer> endIndexs = rootTire.getEndIndexs(lineString);
			indexWidth.add(endIndexs.size());
			if (endIndexs.isEmpty()) {
				continue;
			}
			endIndexs.sort(new Comparator<Integer>() {
				@Override
				public int compare(Integer o1, Integer o2) {
					return o2 - o1;
				}
			});
			sequence.addAll(endIndexs);
		}
	}
	
	private boolean makeSamePosition( List<Integer> sequence, 
			List<Integer> lisPosition, 
			List<Integer> newPosWid,
			List<Integer> oldPosition, 
			List<Integer> newPosition) {
		if (sequence == null 
				|| lisPosition == null 
				|| newPosWid == null
				|| oldPosition == null 
				|| newPosition == null) {
			return  false;
		}
		
		oldPosition.clear();
		
		for (Integer p : lisPosition) {
			if (p >= sequence.size()) {
				return false;
			}
			oldPosition.add(sequence.get(p));
		}
		
		newPosition.clear();
		
		int i = 0;
		int w = newPosWid.get(i);
		for (Integer p : lisPosition) {
			while (p >= w) {
				++i;
				if (i >= newPosWid.size()) {
					break;
				}
				w += newPosWid.get(i);
			}
			if (i >= newPosWid.size()) {
				break;
			}
			newPosition.add(i);
		}
		return true;
	}
	
	private boolean makePatchLineList(List<String> oldLine, 
			List<String> newLine,  
			List<Integer> oldSamePos, 
			List<Integer> newSamePos,
			List<String> patchLine) {
		if (oldLine == null 
				|| newLine == null 
				|| oldSamePos == null 
				|| newSamePos == null
				|| patchLine == null
				|| oldSamePos.size() != newSamePos.size()) {
			return false;
		}
		
		patchLine.clear();
		
		int oldIdx = 0;
		int newIdx = 0;
		for (int i = 0; i < oldSamePos.size(); ++i) {
			for (int j = oldIdx; j < oldSamePos.get(i); ++j) {
				patchLine.add(String.format("%s-   ", j + 1) + oldLine.get(j));
			}
			oldIdx = oldSamePos.get(i) + 1;
			for (int j = newIdx; j < newSamePos.get(i); ++j) {
				patchLine.add(String.format("%s+   ", j + 1) + newLine.get(j));
			}
			newIdx = newSamePos.get(i) + 1;
			patchLine.add(oldLine.get(oldSamePos.get(i)));
		}
		
		for (int j = oldIdx; j < oldLine.size(); ++j) {
			patchLine.add(String.format("%s-   ", j + 1) + oldLine.get(j));
		}
		for (int j = newIdx; j < newLine.size(); ++j) {
			patchLine.add(String.format("%s+  ", j + 1) + newLine.get(j));
		}
		
		return true;
	}
}
